/*
并查集
*/

#include <iostream>
#include <vector>

using namespace std;

class UnionFind {
public:
    UnionFind(int n) {
        this->n = n + 1;
        this->parent = new int[this->n];
        for (int i = 0; i < this->n; i++) {
            parent[i] = -1;
        }
    }

    ~UnionFind() {
        delete[] parent;
    }

    int find(int x) {
        if (parent[x] < 0) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    void merge(int x, int y) {
        // 按树的规模归并，比较没错，根节点元素值小于0，集合元素的个数是负值
        int root_x = find(x);
        int root_y = find(y);
        if (parent[root_y] < parent[root_x]) {
            // y 节点多, x 挂在 y 上，在 y 上加上 x 的节点
            parent[root_y] += parent[root_x]; 
            parent[root_x] = root_y;
        } else {
            parent[root_x] += parent[root_y]; 
            parent[root_y] = root_x;
        }
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int get_set_count(int start) {
        int count = 0;
        for (int i = start; i < n; i++) {
            if (parent[i] < 0) {
                count++;
            }
        }
        return count;
    }

    int get_set_count(int start, int end) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (parent[i] < 0) {
                count++;
            }
        }
        return count;
    }

private:
    int n;
    int *parent;
};